#include <iostream>
#include <vector>

void merge(std::vector<int> & arr ,int left ,int mid,int right){
    std::cout << "broken 1"<<std::endl;
    int n1 = mid -left+1;
    int n2 = right -mid ;
    std::vector<int> arr_l(n1);
    std::vector<int> arr_r(n2);
    std::cout << "broken 1"<<std::endl;
    for (int i = 0;i< n1;i++){
        arr_l[i] = arr[i+left];
    }
    std::cout << "broken 2"<<std::endl;
    for (int i = 0;i< n2;i++){
        arr_r[i] = arr[i+mid+1];
    }
    std::cout << "broken 3"<<std::endl;
    int k = left;
    int i = 0;
    int j = 0;
    while(i<n1 && j<n2){
        if (arr_l[i] < arr_r[j]){
            arr[k] = arr_l[i];
            k++;
            i++;
        } else {
            arr[k] = arr_r[j];
            k++;
            j++;
        }
    }
    while(i<n1){
        arr[k] = arr_l[i];
        k++;
        i++;
    }
    while (j<n2)
    {
        arr[k] = arr_r[j];
        k++;
        j++;
    }
    
}

void merge_sort(std::vector<int> & arr ,int left ,int right){
    if(left >= right){
        return;
    }
    std::cout << "broken 0.5"<<std::endl;
    int mid = int(left + (right-left)/2);
    merge_sort(arr,left,mid);
    merge_sort(arr,mid+1,right);
    merge(arr,left,mid,right);
}

int main(){
    std::cout << "start" <<std::endl;
    std::vector<int> arr = {5,3,1,2,4};
    std::cout << "broken 0"<<std::endl;
    merge_sort(arr,0,4);
    for(int i =0;i<arr.size();i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}